#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> 
#include <cmath>
using namespace std;
typedef long long LL;
const LL MAXN=1e5+6;
bool is_p[MAXN];
LL prime[MAXN/2],p_cnt;
void Init() {
	memset(is_p, 1, sizeof(is_p));
	p_cnt=0;
	for (LL i=2; i<MAXN; ++i) {
		if (is_p[i]) {
			prime[p_cnt++]=i;
		}
		for (LL j=0; j<p_cnt&&i*prime[j]<MAXN; ++j) {
			if (i%prime[j]==0) {
				is_p[i*prime[j]]=false;
				break;
			}
			else {
				is_p[i*prime[j]]=false;
			}
		}
	}
}
LL Euler(LL ask) {
	LL res=1,cnt;
	for (LL i=0; i<p_cnt&&prime[i]<=ask; ++i) {
		if (ask%prime[i]==0) {
			cnt=1;
			while (ask%prime[i]==0) {
				cnt*=prime[i];
				ask=ask/prime[i];
			}
			res*=(cnt-cnt/prime[i]);
		}
	}
	if (ask>MAXN) res*=(ask-1);
	return res;
}
LL POW(LL n, LL q, LL m) {
	LL res=1;
	LL tmp=n%m;
	while (q) {
		if (q&1) {
			res=(res*tmp)%m;
		}
		tmp=(tmp*tmp)%m;
		q=q>>1;
	}
	return res;
}
LL solve(LL n, LL m) {
	if (n%m==0) return 0;
	if (n==1) return 1;
	if (n==2) return 2%m;
	if (n==3) return 9%m;
	if (n==4) return 262144%m;
	LL tmp=Euler(m);
	return POW(n, solve(n-1, tmp)+tmp, m);
}
int main() {
	Init();
	LL n,m;
//	#ifdef hai
//	freopen("in.txt", "r", stdin);
	while (cin>>n>>m) {
		cout<<solve(n,m)<<endl; 
	}
//	#endif
//	#ifndef hai
//	cin.sync_with_stdio(false);
//	cin>>n>>m;
//	cout<<solve(n,m)<<endl;
//	#endif
	return 0;
}
